package leetcode;

/**
 * @author yinlei
 * @date 2018/6/19
 * @since 1.0.0
 */
public class N005LongestPalindromicSubstring {

    public static void main(String[] args) {

        System.out.println(longestPalindrome("babad"));
        System.out.println(longestPalindrome("cbbd"));
        System.out.println(longestPalindrome("cbbbbbd"));
        System.out.println(longestPalindrome("a"));
        System.out.println(longestPalindrome("abcda"));
        System.out.println(longestPalindrome("babadada"));
//        Assert.isTrue("bab".equals(longestPalindrome("babad")), "babad");
    }

    static public String longestPalindrome(String s) {
        if (s.length() < 2) return s;
        char[] chars = s.toCharArray();
        int length = chars.length;

        int longestLow = 0;
        int longestHigh = 1;

        for (int i = 0; i < length; i++) {

            int low = i;
            int high = i;

            // 如果中间字符串为重复字符，则满足回文对称
            while (high < length - 1 && chars[high] == chars[high+1]) {
                high++;
            }

            i = high;

            // 如果存在低位和高位，且两个数值相同，则向两边扩展
            while (low - 1 >= 0 && high + 1 < length && chars[low - 1] == chars[high + 1]) {
                low--;
                high++;
            }

            if (high - low + 1 > longestHigh - longestLow) {
                longestHigh = high + 1;
                longestLow = low;
            }
        }

        return s.substring(longestLow, longestHigh);
    }

//    static public String longestPalindrome(String s) {
//        char[] chars = s.toCharArray();
//        int length = chars.length;
//        String longest = chars[0]+"";
//
//        for (int i = 0; i < length; i++) {
//            for (int j = i + 1; j < length; j++) {
//                if (chars[i] == chars[j]) {
//                    boolean palindromic = true;
//                    for (int x = i + 1, n = i + Math.round((j - i + 1) / 2); x < n; x++) {
//                        if (chars[x] != chars[j + i - x]) {
//                            palindromic = false;
//                            break;
//                        }
//                    }
//                    if (palindromic) {
//                        int nl = j - i + 1;
//                        if (nl > longest.length()) {
//                            longest = String.valueOf(chars, i, nl);
//                        }
//                    }
//                }
//            }
//        }
//        return longest;
//    }
}
